//给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。 
//
// 非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
//输出：13
//解释：
//所有非零偏移下降路径包括：
//[1,5,9], [1,5,7], [1,6,7], [1,6,8],
//[2,4,8], [2,4,9], [2,6,7], [2,6,8],
//[3,4,8], [3,4,9], [3,5,7], [3,5,9]
//下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。
// 
//
// 示例 2： 
//
// 
//输入：grid = [[7]]
//输出：7
// 
//
// 
//
// 提示： 
//
// 
// n == grid.length == grid[i].length 
// 1 <= n <= 200 
// -99 <= grid[i][j] <= 99 
// 
//
// Related Topics 数组 动态规划 矩阵 👍 188 👎 0


package com.tyrone.leetcode.editor.cn;

public class MinimumFallingPathSumIi {
    public static void main(String[] args) {
        Solution solution = new MinimumFallingPathSumIi().new Solution();
        solution.minFallingPathSum(new int[][]{{1,2,3}, {4,5,6}, {7, 8, 9}});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        /**
         * 根据宫水的说法，只用记录上一层的最小值和次小值的下标
         * @param matrix
         * @return
         */
        public int minFallingPathSum(int[][] matrix) {
            int n = matrix.length;
            int[][] dp = new int[2][n];
            int min1 = -1;
            int min2 = -1;
            for (int i = 0; i < n; i++) {
                if (min1==-1 || matrix[0][i]<matrix[0][min1]){
                    min2 = min1;
                    min1 = i;
                } else if (min2==-1 ||matrix[0][i]<matrix[0][min2]) {
                    min2 = i;
                }
                dp[0][i] = matrix[0][i];
            }

            for (int i = 1; i < n; i++) {
                int curMin1 = min1;
                int curMin2 = min2;
                for (int j = 0; j < n; j++) {
                    if (j==curMin1) dp[i & 1][j] = dp[(i-1)&1][curMin2]+matrix[i][j];
                    else dp[i & 1][j] =  dp[(i-1)&1][curMin1]+matrix[i][j];
                }
                min1 = -1;
                min2 = -1;
                for (int j = 0; j < n; j++) {
                    if (min1==-1 ||dp[i&1][j]<dp[i&1][min1]){
                        min2 = min1;
                        min1 = j;
                    } else if (min2==-1 ||dp[i&1][j]<dp[i&1][min2]) {
                        min2 = j;
                    }
                }
            }
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                ans = Math.min(dp[(n - 1) & 1][i], ans);
            }
            return ans;
        }
//    public int minFallingPathSum(int[][] matrix) {
//        int n = matrix.length;
//        int[][] dp = new int[2][n];
//        for (int i = 0; i < n; i++) {
//            dp[0][i] = matrix[0][i];
//        }
//        for (int i = 1; i < n; i++) {
//
//            for (int j = 0; j < n; j++) {
//                dp[i & 1][j] = Integer.MAX_VALUE;
//                for (int k = 0; k < n; k++) {
//                    if (k == j) continue;
//                    dp[i & 1][j] = Math.min(dp[(i - 1) & 1][k] + matrix[i][j], dp[i & 1][j]);
//                }
//            }
//        }
//        int ans = Integer.MAX_VALUE;
//        for (int i = 0; i < n; i++) {
//            ans = Math.min(dp[(n-1)&1][i],ans);
//        }
//        return ans;
//    }
    }
//leetcode submit region end(Prohibit modification and deletion)

}